/* improve_div.h */

#include "spectral_div.h"

#ifndef _IMPROVE_DIV_H_

#define _IMPROVE_DIV_H_

/* 
 *	A single node type definition
 */
typedef struct node
{
	/* node's index */
	int index;
	/* indicates whether this node was already moved */
	int was_moved;
	/* next nodes pointer */
	struct node* next;
}node;

/* 
 *	Nodes list type definition
 */
typedef struct nodes
{
	/* pointer to the list's head */
	node* list;
	/* list size */
	int n;
}nodes;

/*
 *	Compute score of last indices movement
 *	--------------------------------------
 *	B_g:	Part of modularity matrix according to indices in g
 *	s:		The vector that specifies if a vertex belongs to g1 or g2
 *	k_g:	The vector that specifies the degree of each node in g
 *	M:		The sum of all nodes' degrees in A
 *	score:	The vector that specifies each node's score
 *	size:	The size of the score vector
 *	last_removed_index:	-1 if no one moved, o/w the relevant node's index
 */
void compute_score(elem** B_g, elem* s, elem* k_g, elem M, elem* score,
				   int size, int last_removed_index);

/*
 *	Creates a linked list of unmoved nodes
 *	--------------------------------------
 *	size: The number of nodes
 *	last_unmoved: Pointer to the last element in the unmoved list
 *	return: The result list
 *	--------------------------------------------------
 *	(!) The user is responsible of releasing this list
 */
node* create_unmoved(int size, node** last_unmoved);

/*
 *	Turnes the nodes into unmoved state
 *	-----------------------------------
 *	unmoved: The list of nodes
 */
void init_unmoved(node* unmoved);

/*
 *	Removes the max score index from the unmoved list
 *	-------------------------------------------------
 *	unmoved: The list to remove from
 *	max_score_index: The index to remove
 *	last_unmoved_node: Pointer to the last node in the unmoved list
 */
void remove_from_nodes(node** unmoved, int max_score_index, 
					   node** last_unmoved_node);

/*
 *	Releases a list of nodes
 *	------------------------
 *	nodes: Pointer to the list to release
 */
void free_nodes(node* nodes);

/*	
 *	The division to two improvement algorithm 
 *  -----------------------------------------
 *	B_g:	Part of modularity matrix according to indices in g
 *	s:		The vector that specifies if a vertex belongs to g1 or g2
 *	k_g:	The vector that specifies the degree of each node in g
 *	M:		The sum of all nodes' degrees in A
 *	size:	The size of the score vector
 *	return:	The improvement delta
 */
elem improve_2_div(elem** B_g, elem* s, elem* k_g, elem M, int size);

/*	
 *	Returns the max index
 *	---------------------
 *	score:	The vector that specifies each node's score
 *	size:	The size of the score vector
 *	return:	The max index
 */
int calculate_max_index(elem* score, int size);

/* 
 *	Returns the max scored index
 *	----------------------------
 *	score:	 The vector that specifies each node's score
 *	size:	 The size of the score vector
 *	unmoved: All the nodes that weren't moved
 *	return:	 The max scored index
 */
int calculate_max_score_index(elem* score, int size, node* unmoved);

/* 
 *	Creates the vector s
 *	--------------------
 *	g:		 Subgroup of A
 *	g1:		 Subgroup of g
 *	s:		 The vector that specifies if a vertex belongs to g1 or g2
 *	size:	 The g or s vector size
 *	g1_size: The g1 vector size
 */
void create_s (int* g, int* g1, elem* s, int size, int g1_size);

#endif 
